/************************************************************************************************
 * test examples of 100 interesting program in C
 * test 097.c
 * Special Array
 ***********************************************************************************************/

#include <stdio.h>

#define M 8
#define N 4

/*
 *
 */

void print(int* array)
{
    int i;
    for (i = 0; i < N; i++)
        printf("%d ", array[i]);
    printf("\n");
}

int main()
{
    int cur = 0;
    int remain = M;
    int array[N] = {0};
    while (1)
    {
        //printf("%d->", cur);
        //print(array);
        // print and backtrace
        // no need to verify the array, following keep it available
        if (cur == N-1)
        {
            array[cur] = remain;
            print(array);
            array[cur] = 0;
            cur--;
            //printf("backtrace\n");
            continue;
        }
        
        if (array[cur] == (remain+array[cur])/(N-cur))
        {
            // pay attention to this estimation
            // only happen when backtrace
            // to continue backtrace
            if (cur == 0) break;
            else
            {
                remain += array[cur];
                array[cur] = 0;
                cur--;
                //printf("backtrace\n");
            }
        }
        else
        {
            if (cur == 0)
            {
                array[cur]++;
                remain--;
            }
            else if (array[cur] == 0)
            {
                array[cur] = array[cur-1];
                remain -= array[cur-1];
            }
            else
            {
                array[cur]++;
                remain--;
            }
            cur++;
        }
    }            
}

